﻿#pragma once
#include "Index.h"
/**
 * 数组中的逆序对.
 * https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/
 *
 * 在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对.
 * 输入一个数组,求出这个数组中的逆序对的总数.
 * 例如,在数组[7,5,6,4] 中,一共存在5个逆序对.分别是(7,6)(7,5)(7,4)(6,4)(5,4) 
 */
namespace ReverseOrderInArray
{
	class Question
	{
	public:
		virtual int getReverseOrderCount(std::vector<int>& nums) = 0;
	};

	class Merge:public Question
	{
	public:
		int getReverseOrderCount(std::vector<int>& nums) override
		{
			if (nums.empty())
				return 0;
			return mergeDivide(nums, 0, nums.size() - 1);
		}
	private:
		//求在[left,right]范围内逆序对的数量,返回后[left,right]的部分排好序
		int mergeDivide(std::vector<int>& nums,int left,int right)
		{
			if (left >= right)
				return 0;

			int reversePair = 0;
			int mid = left + ((right - left) >> 1);
			reversePair+= mergeDivide(nums, left, mid);
			reversePair += mergeDivide(nums, mid + 1, right);

			//合并[left,mid]和[mid+1,right]两部分
			//两部分分别放尾指针,选出较大值以从后往前的顺序合并
			int part1 = mid;
			int part2 = right;
			//两部分合并后
			std::vector<int> partMerged(right - left + 1, 0);
			int mergeNext = partMerged.size() - 1;

			while(part1>=left || part2>=mid+1)
			{
				if(part2<mid+1)//后部分合并完
				{
					for (int i = mergeNext; i >= 0; --i)
						partMerged[i] = nums[part1--];
					break;
				}
				else if(part1<left)//前部分合并完
				{
					for (int i = mergeNext; i >= 0; --i)
						partMerged[i] = nums[part2--];
					break;
				}
				else
				{
					if(nums[part1]>nums[part2])
					{
						reversePair += part2 - mid;//part2当前剩余的数量
						partMerged[mergeNext--] = nums[part1--];
					}
					else
					{
						partMerged[mergeNext--] = nums[part2--];
					}
				}
			}

			//合并后的内容拷贝到原数组
			for (int i = 0; i < partMerged.size(); ++i)
				nums[left + i] = partMerged[i];

			return reversePair;
		}
	};

	class Practice:public Question
	{
	public:
		int getReverseOrderCount(std::vector<int>& nums) override
		{
			if(nums.empty())
				return 0;

			int reverse_pair_count= reversePairCount(nums,0,nums.size()-1);
			return reverse_pair_count;
		}

	private:
		//在nums指定的范围内,逆序对的数量.
		//当函数返回时,保证nums在[left,right]上已经递增排序
		int reversePairCount(std::vector<int>& nums,int left,int right)
		{
			if(left >= right)
				return 0;
			const int mid=left+((right-left)>>1);

			int pair_count=0;
			pair_count+= reversePairCount(nums,left,mid);
			pair_count+= reversePairCount(nums,mid+1,right);

			//按照从后往前合并两端已有序的数组
			const int size=right-left+1;
			std::vector<int> merged_nums(size,0);
			int merge_index=size-1;

			int first=mid,second=right;
			//两段都在
			while(first>=left && second>=mid+1)
			{
				//前段的数字比后段当前的数字都大,发现逆序对结果
				if(nums[first]>nums[second])
					pair_count+=second-mid;

				//当两段相同时,要让后段的值先被提取
				if(nums[first]>nums[second])
					merged_nums[merge_index--]=nums[first--];
				else
					merged_nums[merge_index--]=nums[second--];
			}
			//前段还在,后段没有
			for(int i=first;i>=left;--i)
				merged_nums[merge_index--]=nums[i];
			//后段还在,前段没有
			for(int i=second;i>=mid+1;--i)
				merged_nums[merge_index--]=nums[i];

			//将合并后的排序数组拷贝到原先的数组
			for(int i=left,merge_index=0;i<=right;++i,++merge_index)
			{
				nums[i]=merged_nums[merge_index];
			}

			return pair_count;
		}
	};

	TEST(ReverseOrderInArrTest, getReverseOrderCount)
	{
		TEST_SOLUTION2(Question,Merge, Practice,&)
		{
			__slnTestor.setTestTimes(100);
			auto nums = TestingUtil::randRangeInts(1000, 0, 1000);

			int expect = 0;
			for(int i=1;i<nums.size();++i)
			{
				for(int j=0;j<i;++j)
				{
					if (nums[j] > nums[i])
						expect++;
				}
			}

			int result= solution->getReverseOrderCount(nums);
			EXPECT_EQ(result, expect);
		};
	}
}